#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

// 非零元素结点结构
typedef struct OLNode
{
    int row,col;
    ElemType value;
    struct OLNode *right,*down;
}OLNode,*OLink;

// 十字链表结构
typedef struct
{
    OLink *rowhead,*colhead;
    int rows,cols,nums;
}CrossList, *PCrossList;

int init_cross_list(PCrossList L, const ElemType *A, int m,int n){
    L->rowhead = (OLink*)malloc(sizeof(OLink) * m);
    for(int i = 0; i < m; i++)
    {
        L->rowhead[i]->right = L->rowhead[i]->down = NULL;
    }
    L->colhead = (OLink*)malloc(sizeof(OLink) * n);
    for(int j = 0; j < n; j++)
    {
        L->colhead[j]->right = L->colhead[j]->down = NULL;
    }
    L->rows = m;
    L->cols = n;
    L->nums = 0;
    
    for(int i = 0; i < m; i++)
    {
        OLink cur = L->rowhead[i];
        for(int j = 0; j < n; j++)
        {
            if(A[i * n + j] != 0)
            {
                OLink newnode = (OLink)malloc(sizeof(OLNode));
                cur->right = newnode;
                cur = cur->right;
                
                OLink temp = L->colhead[j];
                while(temp->down != NULL){temp = temp->down;}
                temp->down = newnode;
                
                cur->row = i + 1;
                cur->col = j + 1;
                cur->value = A[i * n + j];
                cur->right = NULL;
                cur->down = NULL;
                
                L->nums++;
            }
        }
    }
    
    return L->nums;
}


int del_cross_list(PCrossList L, ElemType k){
    //行链表中删除
    for(int i = 0; i < L->rows; i++)
    {
        OLink cur = L->rowhead[i];
        while(cur && cur->right)
        {
            if(cur->right->value == k)
            {
                cur->right = cur->right->right;
            }
            cur = cur->right;
        }
    }
    
    int count = 0;
    //列链表中删除并释放
    for(int j = 0; j < L->cols; j++)
    {
        OLink cur = L->colhead[j];
        while(cur && cur->down)
        {
            if(cur->down->value == k)
            {
                OLink del = cur->down;
                cur->down = cur->down->down;
                free(del);
                count++;
            }
            cur = cur->down;
        }
    }
    
    return count;
}